package 力扣日常刷题.木22一月.第04天0111;

import java.util.*;

/**
 * @author 帅小伙
 * @date 2022/1/11
 * @description
 */
public class Demo03回溯中等括号生成 {


    /*
    * dfs版本
    * */
    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(0,n,new StringBuffer(),0,0);
        return ans;
    }

    void dfs(int index, int n, StringBuffer sb, int r, int l) {
        if (r > n || l > n || r > l) {
            return;
        }
        if (index == 2 * n) {
            ans.add(sb.toString());
        }
        sb.append("(");
        dfs(index+1,n,sb,r,l+1);
        sb.deleteCharAt(sb.length()-1);
        sb.append(")");
        dfs(index+1,n,sb,r+1,l);
        sb.deleteCharAt(sb.length()-1);
    }







    /*
    * 直接找位置拼接字符串
    *
    public List<String> generateParenthesis(int n) {
        if (n == 1) {
            return Arrays.asList("()");
        }
        Set<String> hs = new HashSet<>();
        for (String s : generateParenthesis(n - 1)) {
            for (int i = 0; i < 2*(n-1); i++) {
                hs.add(s.substring(0,i)+"()"+s.substring(i,s.length()));
            }
        }
        return new ArrayList(hs);
    }
     */
}
